package 动态规划;
//https://www.lintcode.com/problem/125/
public class 背包问题二 {
    public int backPackII(int m, int[] a, int[] v) {
        // write your code here
        int[] arr = new int[m + 1];
        for (int i = 0 ; i < a.length ; i++){
            for (int j = m ; j > 0 ; j--){
                if (a[i] <= j){
                    arr[j] = Math.max(arr[j] , arr[j - a[i]] + v[i]);
                }

            }
        }
        return arr[m];

    }
}
